Сжатие данных
Сжатием (компрессией) данных называют преобразование их в форму, занимающую меньше места. В такой форме данные и хранить легче (устройства хранения все-таки не резиновые), и передавать по каналам с ограниченной пропускной способностью куда приятнее.
Все алгоритмы сжатия делятся на два типа: с потерями и без.
Сжатие с потерями позволяет достичь гораздо бóльшей степени сжатия (до 1/30 и менее от исходного объема).
Например, видеофильм, занимающий в неупакованном виде гигабайт 30, удается записать на 1 CD.
Однако, алгоритмы сжатия с потерями приводят к некоторым изменениям самих данных; поэтому применять такие алгоритмы можно только к тем данным, для которых небольшие искажения несущественны: видео, фото-изображения (алгоритмы JPEG), звук (алгоритм MP3).
Сжатие без потерь, конечно, не так эффективно (его степень очень зависит от конкретных данных), зато данные после распаковки полностью идентичны оригинальным. Что абсолютно необходимо, например, для текстовых данных, программного кода. В этой статье будет рассматриваться именно сжатие без потерь.
Большинство алгоритмов сжатия без потерь делятся на две группы: первыесоставляют текст из кусочков исходного файла в той или иной форме (словарные методы); вторые (статистические методы) используют тот факт, что разные символы или символьные группы появляются в файле с разными вероятностями (например, буква "а" в текстовых файлах встречается гораздо чаще, чем "б").
Словарные методы
Словарные методы отличаются высокой скоростью сжатия/распаковки, но несколько худшим сжатием. Словом называется некоторая последовательность символов. В общем - речь, конечно, идет не о символах, а о байтах; но для простоты в примерах будут использоваться ASCII-символы.
Словарь содержит некоторое количество слов (обычно 2x; например, 4096).
Сжатие достигается за счет того, что номер слова в словаре обычно гораздо короче самого слова.
Алгоритмы словарного сжатия делятся на две группы:
1) использующие словарь в явной форме(алгоритмы LZ78, LZW, LZC, LZT, LZMV, LZJ, LZFG)
Например, по словарю
1. "Большинство"
2. "сжатия"
3. "без"
4. "потерь"
5. "алгоритмов"
текст "Большинство алгоритмов сжатия без потерь" сжимается в "15234".
2) указывающие вместо номера слова - позицию относительно текущей позиции и длину повторяющегося участка (алгоритмы LZ77, LZR, LZSS, LZB, LZH)
Например, текст "абаббабаббабвгббабв"
сжимается в "05абабб5504абвг65", где:
"05абабб" – позиция 0 означает, что далее 5 символов идут без сжатия.
"55" – 5 букв с позиции , отстоящей от текущей на 5 символов назад.
"04абвг" – еще 4 символа не сжимается.
"65" –5 букв с позиции , отстоящей от текущей на 6 символов назад.
Модификации LZ-алгоритмов отличаются только способами представления словаря, поиска и добавления слов. Одни сжимают быстрее, но хуже; другие требуют больше памяти.
Рассмотрим подробнее модифицированный алгоритм LZ77.
Архив будет состоять из записей следующего вида:
(n,m) – означает, что с позиции n начинается такая же строка длиной m, что и с текущей позиции.
(0,m,"m символов") – означает, что далее следует m символов, которые не удалось сжать.
Алгоритм сжатия будет заключаться в следующем: ищем в файле место, начиная с которого идет самая длинная последовательность, совпадающая с последовательностью, начинающейся на текущем байте. Если ее длина больше 3, то в архив записываем начало и длину последовательности; иначе - записываем 0, длину последовательности и сами несжатые символы. Распаковка еще проще: пока файл архива не кончился, читаем по 2 числа(n,m). Если n=0, то m символов из архива сразу помещаем в буфер (эти символы нам еще понадобятся) и записываем в выходной файл. Если n<>0 то из буфера с позиции n копируем m элементов в буфер и выходной файл.
Однако есть две проблемы:
1) Ограниченный размер буфера: если нам нужно будет сжать файл размеров в 100МБ, мы его в буфер никак не поместим. Поэтому, когда он будет заполнен (скажем, на 75%), придется сдвинуть данные в нем к на...
